package tree;

/**
 * @Description 111. 二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/
 * @Author Firenut
 * @Date 2023-02-20 19:45
 */
public class T111_minDepth {
    int minLen = Integer.MAX_VALUE;

    // 叶子结点就是左右孩子为null嘛,所以当走道叶子结点的时候就记录一下最大长度
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, 1);
        return minLen;
    }

    // 法2: 自底向上
    int dfs(TreeNode root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        int lLen = Integer.MAX_VALUE, rLen =Integer.MAX_VALUE;
        if (root.left != null) {
            lLen = dfs(root.left);
        }
        if (root.right != null) {
            rLen = dfs(root.right);
        }
        return Math.min(lLen, rLen) + 1;
    }

    // 法1: 自顶向下
    void dfs(TreeNode root,int len){
        if (root.left == null && root.right == null) {
            minLen = Math.min(minLen, len);
            return;
        }
        if (root.left != null) {
            dfs(root.left, len + 1);
        }
        if (root.right != null) {
            dfs(root.right, len + 1);
        }
    }
}